/*
A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.
*/

/**
 * Definition for singly-linked list with a random pointer.
 * struct RandomListNode {
 *     int label;
 *     RandomListNode *next, *random;
 *     RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
 * };
 */
class Solution {
public:
    RandomListNode *copyRandomList(RandomListNode *head) {
        RandomListNode node(-1), *newhead, *shead = head;
        list<RandomListNode *> rlist;
        // first pass, deep copy the list
        for (newhead = &node; head; head = head->next, newhead = newhead->next) {
            newhead->next = new RandomListNode(head->label);
            newhead->next->random = head->random;
            rlist.push_back(head->random);
            head->random = newhead->next;
        }
        // second pass, set random pointer
        for (newhead = node.next; newhead; newhead = newhead->next) {
            if (newhead->random) newhead->random = newhead->random->random;   
        }
        for (head = shead; head; head = head->next) {
            head->random = rlist.front();
            rlist.pop_front(); // remove first elem
        }
        return node.next;
    }
};
